#include <vector>
#include <string>
#include <unordered_map>
// https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked

// 思路：滑动窗口
/*
    1. 使用两个哈希表，一个记录目标字符串p中每个字符的出现次数，另一个记录当前窗口中每个字符的出现次数。
    2. 使用两个指针left和right表示当前窗口的左右边界，初始时都指向字符串s的开头。
    3. 不断移动右指针right，扩大窗口，直到窗口的大小等于p的长度。
    4. 每次移动右指针时，更新窗口中字符的出现次数，并检查当前窗口是否包含了p中的所有字符。
    5. 如果窗口的大小等于p的长度，检查当前窗口是否是p的一个异位词。如果是，则将左指针left的位置加入结果列表中。
    6. 然后移动左指针left，缩小窗口，更新窗口中字符的出现次数，并继续检查当前窗口是否包含了p中的所有字符。
    7. 重复步骤3-6，直到右指针right到达字符串s的末尾。
    8. 返回结果列表。
*/
using namespace std;
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> result;
        unordered_map<char, int> window_map;
        unordered_map<char, int> match_map;
        int match = 0;
        int left = 0;
        int right = 0;
        for (auto c : p) // 构建目标字符串p的字符频率表
            ++match_map[c];
        while (right < s.size()) // 右指针遍历字符串s
        {
            // 1. 移动右指针，扩大窗口
            char c = s[right];      // 当前右指针指向的字符
            ++right;                // 移动右指针，扩大窗口
            if (match_map.count(c)) // 当前字符在目标字符串p中。
            {
                ++window_map[c];                   // 更新窗口中字符的出现次数
                if (window_map[c] == match_map[c]) // 当前字符的出现次数匹配
                    ++match;                       // 更新匹配计数
            }

            // 2. 当窗口大小等于p的长度时，开始移动左指针，缩小窗口
            if (right - left == p.size())
            {
                // 2.1 检查当前窗口是否是p的一个异位词
                if (match == match_map.size())
                {
                    result.push_back(left);
                }
                // 2.2 移动左指针，缩小窗口
                char l = s[left];
                ++left;
                // 2.3 更新窗口中字符的出现次数
                if (window_map.count(l))
                {
                    if (window_map[l] == match_map[l])
                    {
                        --match;
                    }
                    --window_map[l];
                }
            }
        }
        return result;
    }
};